package com.huangpeng.algorithm.dataStructure;

/**
 * @Author huangpeng
 * @Title 二叉查找树的查找操作
 * @Package
 * @Date 2021/7/15 16:15
 * @Description
 * @Version 1.0
 */
public class BinarySearchTree {
    public static class Node{
        private int data;
        private Node left;
        private Node right;

        private Node(int data){
            this.data = data;
        }
    }

    /**
     * 查找操作
     */
    private Node tree;
    public Node find(int data){
        Node p = tree;
        while(p != null){
            if(data < p.data){//如果查找数据小于节点数据则在左子树查找
                p = p.left;
            }else if(data > p.data){//如果查找数据大于节点数据则在左子树查找
                p = p.right;
            }else{//等于查找的数直接返回
                return p;
            }
        }
        return null;
    }

    /**
     * 插入操作
     * @param data
     */
    public void insert(int data){
        if(tree == null){
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while(p != null){
            if(data > p.data){//如果插入的数大于节点数则在右子树遍历插入位置
                if(p.right == null){//右节点为空则插入
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            }else{//如果插入的数小于节点数则在右子树遍历插入位置
                if(p.left == null){//左节点为空则插入
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }

    /**
     * 删除操作
     * @param data
     */
    public void delete(int data){
        Node p = tree;// p 指向要删除的节点，初始化指向根节点
        Node pp = null;// pp 记录的是 p 的父节点
        while(p != null && p.data != data){
            pp = p;
            if(data > p.data){
                p = p.right;
            }else{
                p = p.left;
            }
        }
        if(p == null){// 没有找到
            return;
        }
        // 要删除的节点有两个子节点
        if(p.left != null && p.right != null){// 查找右子树中最小节点
            Node minP = p.right;
            Node minPP = p;// minPP 表示 minP 的父节点
            while(minP.left != null){
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;// 将 minP 的数据替换到 p 中
            p = minP;// 下面就变成了删除 minP 了
            pp = minPP;
        }
        // 删除节点是叶子节点或者仅有一个子节点
        Node child;// p 的子节点
        if(p.left != null){
            child = p.left;
        }else if(p.right != null){
            child = p.right;
        }else{
            child = null;
        }
        // 删除的是根节点
        if(pp == null){
            tree = child;
        }else if(pp.left == p){
            pp.left = child;
        }else{
            pp.right = child;
        }
    }
}
